package lc.q51_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 构建一个二维数组
        int[][] arrs = new int[triangle.size()][triangle.size()];
        // 自底向上
        int size = triangle.size();
        List<Integer> last = triangle.get(size - 1);
        for (int i = 0; i < last.size(); i++) {
            arrs[size - 1][i] = last.get(i);
        }
        // 从最后一个到0
        for (int i = last.size() - 2; i >= 0; i--) {
            List<Integer> integers = triangle.get(i);
            for (int j = 0; j < integers.size(); j++) {
                arrs[i][j] = integers.get(j) + Integer.min(arrs[i + 1][j], arrs[i + 1][j + 1]);
            }
        }
        return arrs[0][0];
    }



    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>(
                Arrays.asList(
                        Arrays.asList(-10),
                        Arrays.asList(-10, 8),
                        Arrays.asList(-10, 8,5),
                        Arrays.asList(100, 80,5,9)
                )
        );
        System.out.println(new Q120().minimumTotal(triangle));
    }
}
